package leetcode_回溯;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/4/16 9:19
 * 累加数
 * 回溯
 * 结束条件：字符串遍历完了，并且数字的个数要 >= 3
 * 两个变量 pre : 前一个数的值 , sum : 前两个数的和 , index : 当前下标
 * 开头难 , 不知道是哪两个数
 * 从头开始遍历所有可能，从第三个数开始
 * 剪枝 -- 数字开头不能为 0
 */
public class _306 {
    public boolean isAdditiveNumber(String num) {
        if (num.length() <= 2) return false;
        return dfs(num, 0, 0, 0, 0);
    }
    public boolean dfs(String num, long pre, long sum, int index, int count) {
        if (index == num.length()) return count >= 3;
        long value = 0;
        for (int i = index; i < num.length(); i++) {
            if (i > index && num.charAt(index) == '0') break;
            value = value * 10 + num.charAt(i) - '0';
            if (count >= 2) {
                if (value < sum) continue;
                else if (value > sum) break;
            }
            if (dfs(num, value, pre + value, i + 1, count + 1)) return true;
        }
        return false;
    }
}




